// https://www.lintcode.com/problem/median-of-two-sorted-arrays/description

class Solution {
public:
    /*
     * @param A: An integer array
     * @param B: An integer array
     * @return: a double whose format is *.5 or *.0
     */
    double findKth(vector<int> &A, vector<int> &B, int startA, int startB, int k)
    {
        if (startA >= A.size())
            return B[startB + k - 1];
        if (startB >= B.size())
            return A[startA + k - 1];
        if (k == 1)
            return min(A[startA], B[startB]);
        int keyA = startA + k / 2 - 1 >= A.size() ? INT_MAX: A[startA + k / 2 - 1];
        int keyB = startB + k / 2 - 1 >= B.size() ? INT_MAX: B[startB + k / 2 - 1];
        if (keyA < keyB)
            return findKth(A, B, startA + k / 2, startB, k - k / 2);
        else
            return findKth(A, B, startA, startB + k / 2, k - k / 2);
    }
    double findMedianSortedArrays(vector<int> &A, vector<int> &B) {
        int sum = A.size() + B.size();
        double res;
        if (sum & 1)
        {
            res = findKth(A, B, 0, 0, sum / 2 + 1);
        } 
        else
        {
            res = (findKth(A, B, 0, 0, sum / 2) + findKth(A, B, 0, 0, sum / 2 + 1)) / 2.0;    
        }
        return res;
    }
};